package warmup.partition;

import java.util.Scanner;

public class Solution
{
	public static void partition(int[] arr)
	{
		if(arr[0] > arr[arr.length-1]){
			int pivot = arr[0];
			int j = arr.length -1;
			int i = arr.length;
			
			while (j >= 1){
				
				while(arr[j] >= pivot){
					i--;
					swap(arr,i,j);
				}
				j--;
			}
			swap(arr,i-1,0);
		}	else {
			//int pivot = arr[arr.length-1];
			//int j = 0;
			//int i = -1;
			
			//while (j <= (arr.length-2)){
			
			//	printArray(arr);
			//	while(arr[j] >= pivot){
			//		i++;
			//		swap(arr,i,j);
			//	}
			//	j++;
			//}
			
			//swap(arr,i++,arr.length-1);
		int left = 0;
        int right = arr.length-1;
        int pivot = arr[left];
        int pivotIndex = left;
       
        left++;
        while(left < right)
        {
            while (arr[left] < pivot){
                left++;
            }
            while(arr[right] > pivot){
                right--;
            }
            if(left < right){
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
            left ++;
            right --;
        }
        arr[pivotIndex] = arr[right+1];
        arr[right+1] = pivot;      
		}
	}
	
	public static void swap(int[] arr, int i, int j){
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] =temp;
	}
	
	public static void printArray( int[] arr){
		
		for(int n:arr){
			System.out.print(n + " ");
		}
		System.out.println();
	}
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();
		int n = Integer.parseInt(line);
		
		line = sc.nextLine();
		String[] numbers = line.split(" ");
		int[] arr = new int[n];		
		
		for(int i = 0; i < n ; i++){
				arr[i] = Integer.parseInt(numbers[i]);				
		}
		
		partition(arr);
		
		printArray(arr);
	}
}